public class RainTrap {
    public int trap(int height[]) {
        int n = height.length;
        int leftMaxHeight[] = new int[n];
        int rightMaxHeight[] = new int[n];
        int res = 0;
        leftMaxHeight[0] = height[0];
        rightMaxHeight[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            leftMaxHeight[i] = Math.max(leftMaxHeight[i - 1], height[i]);
        }

        for (int i = n - 2; i >= 0; i--) {
            rightMaxHeight[i] = Math.max(rightMaxHeight[i + 1], height[i]);
        }

        for (int i = 1; i < n - 1; i++) {
            res += Math.min(leftMaxHeight[i], rightMaxHeight[i]) - height[i];
        }
        return res;


    }
}
